/******************************************************************************
 *  Date:
 *      March 2011
 *
 *  Authors:
 *      Tomasz Jankowski 171073
 *
 *  Puprose:
 *      An academic project on Univercity of technologi in Wroclaw.
 *
 ******************************************************************************/
 
#ifndef HEAP_HPP
#define HEAP_HPP

#include <cstring>
#include <cassert>
#include <utility>

template<typename T_key, typename T_data> class Heap
{
    public:
        typedef std::pair<T_key, T_data> Node;
        
        Heap (unsigned int size) :
            elements_count (0),
            array (reinterpret_cast<Node*> (malloc (sizeof (Node) * size))),
            array_size (size)
        {
            // ...
        }
        
        Heap (unsigned int size,
              unsigned int elements_count) :
            elements_count (elements_count),
            array (reinterpret_cast<Node*> (malloc (sizeof (Node) * size))),
            array_size (size)
        {
        
            // ...
        }
        
        ~Heap (void)
        {
            free (this->array);
        }
        
        Node& operator [] (unsigned int i)
        {
            return this->array [i];
        }
        
        unsigned int size (void) const
        {
            return this->elements_count;
        }
        
        Node extract_min (void)
        {
            assert (this->elements_count != 0);
            
            Node minimal = this->array [0];
            
            this->array [0] = this->array [this->elements_count-1];
                             
            this->elements_count--;  
                                   
            this->heapify (1);  
                     
            return minimal;
        }
        
        void insert (T_key  key, 
                     T_data data)
        {
            this->elements_count++; 
            
            if (sizeof (Node) * (this->elements_count + 1) > this->array_size)
            {
                this->array_size += 10 * sizeof (Node);
                this->array = reinterpret_cast<Node*> (realloc (this->array, this->array_size));
            }
            
            unsigned int i (this->elements_count);
            
            while (i > 1 && this->array [parent (i) - 1].first > key)
            {
                this->array [i-1] = this->array [parent (i)-1];
                i = parent (i);
            }
            
            this->array [i-1].first = key;
            this->array [i-1].second = data;
        }
        
        void heapify (unsigned int i)
        {
            unsigned int left_i (left (i));
            unsigned int right_i (right (i));
            unsigned int minimal_i (-1);
            Node         tmp_node;
            
            if (left_i <= this->elements_count && 
                this->array [left_i-1].first < this->array [i-1].first)
            {
                minimal_i = left_i;
            }
            else
            {
                minimal_i = i;
            }
            
            if (right_i <= this->elements_count && 
                this->array [right_i-1].first < this->array [minimal_i-1].first)
            {
                minimal_i = right_i;
            }
            
            if (minimal_i != i)
            {
                tmp_node = this->array [i-1];
                
                this->array [i-1] = this->array [minimal_i-1];
                this->array [minimal_i-1] = tmp_node;
                
                this->heapify (minimal_i);
            }
        }
        
        void decrease_key (unsigned int i,
                           T_key        key)
        {
            if (key < this->array[i].first)
            {
                Node temp;
			
			    this->array[i].first = key;
			
			    while (i > 1 && this->array[parent (i)] > this->array [i])
			    {
				    temp = array[i];
				    array[i] = array[parent(i)];
				    array[parent(i)] = temp;
				    i = parent (i);
			    }
		    }
		}
        
    private:            
        static unsigned int parent (unsigned int i)
        {
            return i >> 1;
        }
        
        static unsigned int right (unsigned int i)
        {
            return i << 1;
        }
        
        static unsigned int left (unsigned int i)
        {
            return (i << 1) + 1;
        }
        
        unsigned int root;
        
        Node*        array;
        unsigned int elements_count;
        unsigned int array_size;
};

#endif // HEAP_HPP
